Low-power and Lossy Networks (LLNs), e.g., sensor networks, have a myriad of applications, such as smart grid, smart cities, home and building automation, etc. Various challenges are presented with LLNs, such as lossy links, low bandwidth, battery operation, low memory and/or processing capability, etc. Large-scale IP smart object networks pose a number of technical challenges. For instance, the degree of density of such networks (such as Smart Grid networks with a large number of sensors and actuators, smart cities, or advanced metering infrastructure or “AMI” networks) may be extremely high: it is not rare for each node to see several hundreds of neighbors. Also, links are usually shared (e.g., using wireless mesh or powerline communication (PLC) networks) and provide very limited capacity (from a few Kbits/s to a several dozens of KBits/s).
The computation of diverse paths is a well-known technical challenge in networks using distance vector routing protocols, such as many LLN routing protocols. The ability to build diverse paths is important for the Internet of Things (IoT) for a number of critical/real-time applications where “1+1” techniques consisting of duplicating critical packets and sending them along diverse paths is a strong requirement. Indeed, for such packets, links are so lossy that sending a single copy along a path has a high probability of being lost (and being retransmitted, which involves additional delays), especially when the path diameter increases, particularly since the path's Packet Error Rate (PER) increases exponentially with the path length. Note that the computation of diverse paths may also be used to load-balance traffic flows across diverse paths (not just for 1+1).
Because LLNs, as well as other networks, often operate with devices that have strict memory constraints, many networks use source routing to deliver packets to their destination. Source routing allows the network to concentrate routing state at one or a few more capable devices in the network (typically a border router). One method for multi-path forwarding with source routing is to discover and maintain multiple paths towards a destination at the source. Then when sending a packet, each copy of the packet includes a different source route. However, doing so is difficult and costly to do in practice. Distance vector routing protocols typically used with LLNs are not well-suited at building completely diverse paths. Using multi-path forwarding with source routing assumes that the routing protocol is capable of building multiple routes towards a single destination. If the routing protocol is not capable of doing this, then multi-path forwarding cannot be used.